package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

/**
 * Created by angela on 6/8/2014.
 */
public class CommonNodeInTree {

    public static TreeNode findCommonNode(TreeNode treeNode,TreeNode left, TreeNode right){
        TreeNode result = new TreeNode();
        findChildNode(treeNode,left,right,result);
        return result.getLeft();
    }

    private static int findChildNode(TreeNode treeNode,TreeNode left, TreeNode right,TreeNode result){
        if(treeNode.getValue()==left.getValue()||treeNode.getValue()==right.getValue()){
            return 1;
        }
        if(treeNode.getLeft()==null && treeNode.getRight()==null){
            return 0;
        }
        int sum = findChildNode(treeNode.getLeft(),left,right,result)+findChildNode(treeNode.getRight(),left,right,result);
        if(sum==2&& result.getLeft()==null){
            result.setLeft(treeNode);
        }
        return sum;
    }

    public static void main(String[] arg){
        System.out.print("Result: "+ findCommonNode(TreeBuilder.createTreeByArrayInWidth(new int[]{1, 2, 3, 4, 5, 6, 7}), new TreeNode(4),new TreeNode(7)).getValue());
    }
}
